//Program to demonstrate linked list operations

#include<stdio.h>
#include<malloc.h>

struct node
{
	int data;
	struct node *next;
};


struct node *appended(struct node *q, int num)
{
	struct node *new_node;
	new_node=malloc(sizeof(struct node));
	if(new_node==NULL)
	{
		printf("\n Error : malloc failed in add_to_list");
	}
	new_node->data=num;
	new_node->next=q;
	return new_node;
}


void insertbegin(struct node *q,int num)
{
	struct node *node,*temp;
	node=malloc(sizeof(struct node));
	node->data=num;
	if(q!=NULL)
	{
                 node->next=q;
                 q=node;
        }
        else
        {
	        q=temp=node;
	        node->next=NULL;
        }
}
	
	 
void insertpos(struct node *q,int num, int pos)
{
	struct node *node,*temp;	
	int i;
        if(pos==1)
        {
 	       insertbegin(q,num);
	       return;
	}
	temp=q;
	printf("%d",temp->data);
	
        node=malloc(sizeof(struct node));
        node->data=num;
	 
	for(i=1;i<pos-1;i++)
	     temp=temp->next;
	     node->next=temp->next;
	     temp->next=node;
}

void display(struct node *pt)
{
	while(pt!=NULL)
	{
		printf(" Data : %d",pt->data);
		pt=pt->next;
	}
}


struct node *reverse(struct node *ptr1)	
{

	struct node *temp1 = ptr1;
	struct node *temp2 = NULL;
	struct node *temp3 = NULL;

	while ( temp1 )
	{
		ptr1 = temp1; //set the head to last node		
		temp2= temp1->next; // save the next ptr in temp2
		temp1->next = temp3; // change next to privous
		temp3 = temp1;
		temp1 = temp2;
	}
 
	return ptr1;
}


//	CONCATENATION OF LINKED LISTS

struct node *extend(struct node *p,struct node *q)
{
	struct node *x,*r;

	if (p==NULL)
	r=q;

	if (q==NULL)
	r=p;
	else
	{
      		x=p;
      		r=x;
      		while(x->next!=NULL)
	 	x=x->next;
      		x->next=q;
	}
    	return(r);
}


// SEARCHING AN ELEMENT IN THE LINKED LIST
// THIS FUNCTION FINDS THE FIRST OCCURENCE OF
// A DATA AND RETURNS A POINTER TO ITS ADDRESS

int count(struct node *p,int num)
{
	struct node *temp;
	int count;
	count=1;
	temp = p;
	//printf("\nLink of temp %u", temp->next);
	while(temp->next!=NULL)
	{
		if(temp->data == num)
			count++;
		temp=temp->next;
	}
	return count;
}

int indexed(struct node *p,int num)
{
	struct node *temp;
	int index;
	index=0;
	temp = p;
	while(temp->next!=NULL)
	{
		if(temp->data == num)
			return index;
		temp=temp->next;
		index++;
	}
}

// DELETING DATA FROM THE LINKED LIST//

void delete(struct node *p,int num)
{
	struct node *temp,*x;
	temp=p;
	x= NULL;

	while (temp->next !=NULL)
	{
		if(temp->data == num)
		{
			if (x==NULL)
			{
				p = temp->next;
				free(temp);
				return;
			}
			else
			{
				x->next = temp->next;
				free(temp);
				return;
			}
		}                  //end of outer if
		x=temp;
		temp=temp->next;
	}	//end of while
	printf("\nNo such entry to delete ");
}	//end of fn.


struct node *pop(struct node *p,int num)
{
	struct node *temp,*x,*y;
	temp=p;
	x= NULL;
	int index;
	index=0;

	while (temp->next !=NULL)
	{
		if(index == num)
		{
			if (x==NULL)
			{
				p = temp->next;
				free(temp);
				return;
			}
			else 
			{
				y=x;				
				x->next = temp->next;
				free(temp);
				return y;
			}
		}        
	        //end of outer if
		x=temp;
		temp=temp->next;
		index++;
	}	//end of while
	//deleting the last entry
	printf("\nNo such entry to delete ");
}

/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) 
{
	struct node *head_three;

	if(head_one == NULL)
	return head_two;

	if(head_two == NULL)
	return head_one;

	if(head_one->data < head_two->data) 
	{
		head_three = head_one;
		head_three->next = merge(head_one->next, head_two);
	} 
	else 
	{
		head_three = head_two;
		head_three->next = merge(head_one, head_two->next);
	}

	return head_three;
} 


/* preform merge sort on the linked list */
struct node *mergesort(struct node *ptr1) 
{
	struct node *head_one;
	struct node *head_two;

	if((ptr1 == NULL) || (ptr1->next == NULL))
		return ptr1;

	head_one = ptr1;
	head_two = ptr1->next;
	while((head_two != NULL) && (head_two->next != NULL)) 
	{
		ptr1 = ptr1->next;
		head_two = ptr1->next->next;
	}
	head_two = ptr1->next;
	ptr1->next = NULL;

	return merge(mergesort(head_one), mergesort(head_two));
}


void main()
{
	int choice,always,num,pos;

	struct node *ptr1,*ptr2,*ptr3,*result,*temp;

	ptr1=NULL;
	ptr2=NULL;
	ptr3=NULL;
	result=NULL;		//result for storing the result of concatenation

	always=1;

	while(always=1)
	{
		printf("		Main Menu              \n\n");
		printf("1.Append element\n");                         
		printf("2.Delete element\n");
		printf("3.Extend Linked List\n");
		printf("4.Reverse linked list\n");
	        printf("5.Sort linked list\n");
		printf ("6. Count of a no. in Linked List.\n");
		printf ("7. Index of a no. in Linked List.\n");
		printf ("8. Pop a no. in Linked List.\n");
		printf ("9. Insert a no. in Linked List.\n");
		printf("10.Display elements\n");
		printf("Please enter the choice : ");
		scanf("%d",&choice);
		switch(choice)
		{
			case 1:	printf("\nEnter the element you want to append   ");
				scanf("%d",&num);
				ptr1=reverse(ptr1);				
				ptr1=appended(ptr1,num);
				ptr1=reverse(ptr1);
				display(ptr1);
				break;
			case 2:	printf("\nEnter the element to delete ");
				scanf("%d",&num);
				delete(ptr1,num);
				display(ptr1);
				break;
			case 3: /* Inputs given internally for demo only */
				printf(" Now demonstrating linked list concatenation Press any key to continue...");
				ptr2=appended(ptr2,2);
				ptr2=appended(ptr2,4);
				ptr2=appended(ptr2,6);
				printf("\nDisplaying second Linked List");
				display(ptr2);
				result = extend(ptr1,ptr2);
				printf("\nNow Displaying the result of concatenation");
				display(result);
				break;
			case 4: printf("\nInverting the list ...Press any key to continue...");
				ptr1=reverse(ptr1);
				display(ptr1);
				break;
			case 5: printf("\nSorting the list ...Press any key to continue...");
				ptr1=mergesort(ptr1);
				display(ptr1);
				break;
			case 6: printf("\nEnter the element you want to count   ");
				scanf("%d",&num);
				printf("\nCounting the data in the list ...Press any key to continue...");
				num=count(ptr1,num);
				printf("%d",num);
				break;
			case 7: printf("\nEnter the element   ");
				scanf("%d",&num);
				printf("\nFinding index of the chosen no. from the list ...Press any key to continue...");
				num=indexed(ptr1,num);
				printf("%d",num);
				break;
			case 8: printf("\nEnter the element you want to pop   ");
				scanf("%d",&num);
				printf("\nPopping the chosen no. from the list ...Press any key to continue...");
				ptr3=pop(ptr1,num);
				display(ptr3);
				//printf("%d",num);
				break;
			case 9: printf("\n Enter the position where u wanna insert ur element : ");
				scanf("%d",&pos);
				printf("\n Enter the element u wanna insert : ");
				scanf("%d",&num);
				insertpos(ptr1,num,pos);
			case 10: display(ptr1);
				break;
			default:printf("\nWrong  choice");
		}
		printf("\nDo you want to continue ( press 1 for yes 0 for no)");
		scanf("%d",&always);
	}		//end of while
}



